'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-23 22:10:38
'''
'''
968. 监控二叉树
难度
困难

223

收藏

分享
切换为英文
关注
反馈
给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

 

示例 1：



输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：



输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

tips:这个关键点是记录维护三种状态（我开始想的是动态规划，其实一样，开始想的是从头到尾的动态规划。
可以想一下从尾到头的动态规划（回溯），对于一个点root来说，想要得到他的全覆盖，需要它的left与right提供
点什么信息呢？需要a.left点覆盖时的总数左子树照相机总数，b.left点覆盖不覆盖时左子树照相机总数以及
c.left点的左子树与右子树全被覆盖时的照相机总数。right点相同。这相当于确定了状态，接下来是状态转移方程。
状态转移方程可以根据状态定义直接得到
a = lc + rc +1
b = min([a, la+rb, ra+lb])
c = min(a, lb + rb)
如此，回溯代码如下：
'''
from tree_node import *
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        from sys import maxsize
        def recurese(root):
            if not root:
                return maxsize, 0, 0
            la, lb, lc = recurese(root.left)
            ra, rb, rc = recurese(root.right)
            a = lc + rc + 1
            b = min([a, la+rb, ra+lb])
            c = min(a, lb + rb)
            return a, b, c
        return recurese(root)[1]
if __name__ == "__main__":
    null = 'null'
    root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    solution = Solution()
    print(solution.minCameraCover(root))